using BepuUtilities;
using BepuUtilities.Collections;
using BepuUtilities.Memory;
using System;
using System.Diagnostics;
using System.Runtime.CompilerServices;
using System.Threading;
#if MYCODE
using BepuUtilities.Vectors;
#else
using System.Numerics;
#endif
namespace BepuPhysics.Trees
{
    partial struct Tree
    {
        /// <summary>
        /// 缓存输入和输出,以便以多线程方式执行树的重新调整和优化操作。
        /// </summary>
        public class RefitAndRefineMultithreadedContext
        {
            Tree Tree;

            int RefitNodeIndex;
            QuickList<int> RefitNodes;
            float RefitCostChange;

            int RefinementLeafCountThreshold;
            Buffer<QuickList<int>> RefinementCandidates;
            Action<int> RefitAndMarkAction;

            int RefineIndex;
            QuickList<int> RefinementTargets;
            int MaximumSubtrees;
            Action<int> RefineAction;

            QuickList<int> CacheOptimizeStarts;
            int PerWorkerCacheOptimizeCount;
            Action<int> CacheOptimizeAction;

            IThreadDispatcher threadDispatcher;

            public RefitAndRefineMultithreadedContext()
            {
                RefitAndMarkAction = RefitAndMark;
                RefineAction = Refine;
                CacheOptimizeAction = CacheOptimize;
            }

            public unsafe void RefitAndRefine(ref Tree tree, BufferPool pool, IThreadDispatcher threadDispatcher, int frameIndex,
                float refineAggressivenessScale = 1, float cacheOptimizeAggressivenessScale = 1)
            {
                if (tree.leafCount <= 2)
                {
                    // 如果有2个或更少的树叶,则REFIT/REFINE/CACHE OPTIMIZE根本不执行任何操作。
                    // (根节点没有父节点,因此它没有边界框,并且无论我们如何交换根节点的子节点,SAH都不会改变。)
                    // 避免这种情况也为另一个代码路径提供了一个保证,即它将使用具有两个子节点的节点。
                    return;
                }
                this.threadDispatcher = threadDispatcher;
                Tree = tree;
                // 请注意,我们创建了每个线程的优化候选项。这是因为候选人是在多线程改装和标记阶段找到的,并且
                // 我们不想把时间花在同步工作上。然后,候选者被削减到为精炼通过设定的目标单个目标。
                pool.Take(threadDispatcher.ThreadCount, out RefinementCandidates);
                Tree.GetRefitAndMarkTuning(out MaximumSubtrees, out var estimatedRefinementCandidateCount, out RefinementLeafCountThreshold);
                // 请注意,重新调整节点的数量不一定受MaximumSubtree的限制。这只是一个试探性的估计。必须支持调整大小。
                RefitNodes = new QuickList<int>(MaximumSubtrees, pool);
                // 请注意,我们没有严格保证最大优化计数,因此工作人员可能需要调整每个线程的优化候选列表的大小。
                for (int i = 0; i < threadDispatcher.ThreadCount; ++i)
                {
                    RefinementCandidates[i] = new QuickList<int>(estimatedRefinementCandidateCount, threadDispatcher.GetThreadMemoryPool(i));
                }

                int multithreadingLeafCountThreshold = Tree.leafCount / (threadDispatcher.ThreadCount * 2);
                if (multithreadingLeafCountThreshold < RefinementLeafCountThreshold)
                    multithreadingLeafCountThreshold = RefinementLeafCountThreshold;
                CollectNodesForMultithreadedRefit(0, multithreadingLeafCountThreshold, ref RefitNodes, RefinementLeafCountThreshold, ref RefinementCandidates[0],
                    pool, threadDispatcher.GetThreadMemoryPool(0));

                RefitNodeIndex = -1;
                threadDispatcher.DispatchWorkers(RefitAndMarkAction);
                // 将候选集合压缩成一组目标。
                int refinementCandidatesCount = 0;
                for (int i = 0; i < threadDispatcher.ThreadCount; ++i)
                {
                    refinementCandidatesCount += RefinementCandidates[i].Count;
                }
                Tree.GetRefineTuning(frameIndex, refinementCandidatesCount, refineAggressivenessScale, RefitCostChange,
                    out var targetRefinementCount, out var period, out var offset);
                RefinementTargets = new QuickList<int>(targetRefinementCount, pool);

                // 请注意,只有所有精化*候选者*的子集将成为精化*目标*。
                // 我们从半随机偏移开始,然后跳过集合来累积目标。
                // 成为目标的候选数量基于精化攻击性,
                // 根据用户输入(比例)和树的波动性(RefitCostChange)进行调整。
                var currentCandidatesIndex = 0;
                int index = offset;
                for (int i = 0; i < targetRefinementCount - 1; ++i)
                {
                    index += period;
                    // 如果索引不适合,则绕回。
                    while (index >= RefinementCandidates[currentCandidatesIndex].Count)
                    {
                        index -= RefinementCandidates[currentCandidatesIndex].Count;
                        ++currentCandidatesIndex;
                        if (currentCandidatesIndex >= threadDispatcher.ThreadCount)
                            currentCandidatesIndex -= threadDispatcher.ThreadCount;
                    }
                    Debug.Assert(index < RefinementCandidates[currentCandidatesIndex].Count && index >= 0);
                    var nodeIndex = RefinementCandidates[currentCandidatesIndex][index];
                    Debug.Assert(Tree.Metanodes[nodeIndex].RefineFlag == 0, "Refinement target search shouldn't run into the same node twice!");
                    RefinementTargets.AddUnsafely(nodeIndex);
                    Tree.Metanodes[nodeIndex].RefineFlag = 1;
                }
                // 请注意,只有在之前未将根节点拾取为目标时,才会细化该根节点。
                if (Tree.Metanodes[0].RefineFlag != 1)
                {
                    RefinementTargets.AddUnsafely(0);
                    Tree.Metanodes[0].RefineFlag = 1;
                }
                RefineIndex = -1;

                threadDispatcher.DispatchWorkers(RefineAction);
                // 请注意,我们将REFINE标志推迟到细化完成之后才清除。如果我们是在精炼行动本身做的话,
                // 它将通过允许根据它们的完成顺序进行细化来引入非确定性。
                for (int i = 0; i < RefinementTargets.Count; ++i)
                {
                    Tree.Metanodes[RefinementTargets[i]].RefineFlag = 0;
                }

                // 要实现多线程,需要为每个工作进程分配一个连续的节点块。您希望尽可能使用最大的块来链接像样的缓存行为。
                // 请注意,线程越多,需要进行的缓存优化就越多,因为分散得越多,其有效性就会略有降低。
                var cacheOptimizeCount = Tree.GetCacheOptimizeTuning(MaximumSubtrees, RefitCostChange, (Math.Max(1, threadDispatcher.ThreadCount * 0.25f)) * cacheOptimizeAggressivenessScale);

                var cacheOptimizationTasks = threadDispatcher.ThreadCount * 2;
                PerWorkerCacheOptimizeCount = cacheOptimizeCount / cacheOptimizationTasks;
                var startIndex = (int)(((long)frameIndex * PerWorkerCacheOptimizeCount) % Tree.nodeCount);
                CacheOptimizeStarts = new QuickList<int>(cacheOptimizationTasks, pool);
                CacheOptimizeStarts.AddUnsafely(startIndex);

                var optimizationSpacing = Tree.nodeCount / threadDispatcher.ThreadCount;
                var optimizationSpacingWithExtra = optimizationSpacing + 1;
                var optimizationRemainder = Tree.nodeCount - optimizationSpacing * threadDispatcher.ThreadCount;

                for (int i = 1; i < cacheOptimizationTasks; ++i)
                {
                    if (optimizationRemainder > 0)
                    {
                        startIndex += optimizationSpacingWithExtra;
                        --optimizationRemainder;
                    }
                    else
                    {
                        startIndex += optimizationSpacing;
                    }
                    if (startIndex >= Tree.nodeCount)
                        startIndex -= Tree.nodeCount;
                    Debug.Assert(startIndex >= 0 && startIndex < Tree.nodeCount);
                    CacheOptimizeStarts.AddUnsafely(startIndex);
                }

                threadDispatcher.DispatchWorkers(CacheOptimizeAction);

                for (int i = 0; i < threadDispatcher.ThreadCount; ++i)
                {
                    // 请注意线程内存池的使用。由于可以调整大小,因此每个线程都为列表分配了自己的内存。
                    RefinementCandidates[i].Dispose(threadDispatcher.GetThreadMemoryPool(i));
                }
                pool.Return(ref RefinementCandidates);
                RefitNodes.Dispose(pool);
                RefinementTargets.Dispose(pool);
                CacheOptimizeStarts.Dispose(pool);
                Tree = default;
                this.threadDispatcher = null;
            }

            unsafe void CollectNodesForMultithreadedRefit(int nodeIndex,
                int multithreadingLeafCountThreshold, ref QuickList<int> refitAndMarkTargets,
                int refinementLeafCountThreshold, ref QuickList<int> refinementCandidates, BufferPool pool, BufferPool threadPool)
            {
                ref var node = ref Tree.Nodes[nodeIndex];
                ref var metanode = ref Tree.Metanodes[nodeIndex];
                ref var children = ref node.A;
                Debug.Assert(metanode.RefineFlag == 0);
                Debug.Assert(Tree.leafCount > 2);
                for (int i = 0; i < 2; ++i)
                {
                    ref var child = ref Unsafe.Add(ref children, i);
                    if (child.Index >= 0)
                    {
                        // 每个节点存储多线程改装中涉及的子项的数量。
                        // 这允许后期以线程安全的方式爬树。
                        ++metanode.RefineFlag;
                        if (child.LeafCount <= multithreadingLeafCountThreshold)
                        {
                            if (child.LeafCount <= refinementLeafCountThreshold)
                            {
                                // 波前节点可能在树中有这么高,所以必须在这里捕获它,因为后期传递找不到它。
                                refinementCandidates.Add(child.Index, threadPool);
                                // 编码子索引告诉线程使用RefitAndMeasure而不是RefitAndMark,因为这是一个Wavefront节点。
                                refitAndMarkTargets.Add(Encode(child.Index), pool);
                            }
                            else
                            {
                                refitAndMarkTargets.Add(child.Index, pool);
                            }
                        }
                        else
                        {
                            CollectNodesForMultithreadedRefit(child.Index, multithreadingLeafCountThreshold, ref refitAndMarkTargets, refinementLeafCountThreshold, ref refinementCandidates, pool, threadPool);
                        }
                    }
                }
            }

            unsafe void RefitAndMark(int workerIndex)
            {
                // 因为可能会调整大小,所以我们必须使用线程的缓冲池。
                // 主线程已经使用工作线程池创建了优化候选列表。
                var threadPool = threadDispatcher.GetThreadMemoryPool(workerIndex);
                int refitIndex;
                Debug.Assert(Tree.leafCount > 2);
                while ((refitIndex = Interlocked.Increment(ref RefitNodeIndex)) < RefitNodes.Count)
                {

                    var nodeIndex = RefitNodes[refitIndex];
                    bool shouldUseMark;
                    if (nodeIndex < 0)
                    {
                        // 节点已标记为波前。应继续执行RefitAndMeasure,而不是RefitAndMark。
                        nodeIndex = Encode(nodeIndex);
                        shouldUseMark = false;
                    }
                    else
                    {
                        shouldUseMark = true;
                    }

                    ref var node = ref Tree.Nodes[nodeIndex];
                    ref var metanode = ref Tree.Metanodes[nodeIndex];
                    Debug.Assert(metanode.Parent >= 0, "The root should not be marked for refit.");
                    ref var parent = ref Tree.Nodes[metanode.Parent];
                    ref var childInParent = ref Unsafe.Add(ref parent.A, metanode.IndexInParent);
                    if (shouldUseMark)
                    {
                        var costChange = Tree.RefitAndMark(ref childInParent, RefinementLeafCountThreshold, ref RefinementCandidates[workerIndex], threadPool);
                        metanode.LocalCostChange = costChange;
                    }
                    else
                    {
                        var costChange = Tree.RefitAndMeasure(ref childInParent);
                        metanode.LocalCostChange = costChange;
                    }


                    // int find LeafCount;
                    // Tree.Validate(RefitNodes.Elements[refitNodeIndex],Node->Parent,Node->IndexInParent,ref*bindingBoxInParent,out find LeafCount);


                    // 走到树上去。
                    node = ref parent;
                    metanode = ref Tree.Metanodes[metanode.Parent];
                    while (true)
                    {

                        if (Interlocked.Decrement(ref metanode.RefineFlag) == 0)
                        {
                            // 计算子节点对此节点卷更改的贡献。
                            ref var children = ref node.A;
                            metanode.LocalCostChange = 0;
                            for (int i = 0; i < 2; ++i)
                            {
                                ref var child = ref Unsafe.Add(ref children, i);
                                if (child.Index >= 0)
                                {
                                    ref var childMetadata = ref Tree.Metanodes[child.Index];
                                    metanode.LocalCostChange += childMetadata.LocalCostChange;
                                    // 清除优化旗帜(联合)。
                                    childMetadata.RefineFlag = 0;

                                }
                            }

                            // 此线程是访问此节点的最后一个线程,因此它必须处理此节点。
                            // 将所有子边界框合并为一个。
                            if (metanode.Parent < 0)
                            {
                                // 根节点。
                                // 不必费心将根的音量变化包括在内。
                                // 精化不能改变根的界限,所以世界变大或变小的事实
                                // 实际上对应该做多大的改进没有任何影响。
                                // 但是,我们需要除以根体积,这样我们就可以得到成本度量的变化,而不是体积的变化。
                                var merged = new BoundingBox { Min = new Vector3(float.MaxValue), Max = new Vector3(float.MinValue) };
                                for (int i = 0; i < 2; ++i)
                                {
                                    ref var child = ref Unsafe.Add(ref children, i);
                                    BoundingBox.CreateMerged(child.Min, child.Max, merged.Min, merged.Max, out merged.Min, out merged.Max);
                                }
                                var postmetric = ComputeBoundsMetric(ref merged);
                                if (postmetric > 1e-9f)
                                    RefitCostChange = metanode.LocalCostChange / postmetric;
                                else
                                    RefitCostChange = 0;
                                // 清除根的优化标志(联合)。
                                metanode.RefineFlag = 0;
                                break;
                            }
                            else
                            {
                                parent = ref Tree.Nodes[metanode.Parent];
                                childInParent = ref Unsafe.Add(ref parent.A, metanode.IndexInParent);
                                var premetric = ComputeBoundsMetric(ref childInParent.Min, ref childInParent.Max);
                                childInParent.Min = new Vector3(float.MaxValue);
                                childInParent.Max = new Vector3(float.MinValue);
                                for (int i = 0; i < 2; ++i)
                                {
                                    ref var child = ref Unsafe.Add(ref children, i);
                                    BoundingBox.CreateMerged(child.Min, child.Max, childInParent.Min, childInParent.Max, out childInParent.Min, out childInParent.Max);
                                }
                                var postmetric = ComputeBoundsMetric(ref childInParent.Min, ref childInParent.Max);
                                metanode.LocalCostChange += postmetric - premetric;
                                node = ref parent;
                                metanode = ref Tree.Metanodes[metanode.Parent];
                            }
                        }
                        else
                        {
                            // 此线程不是最后一个访问此节点的线程,因此它应该会死亡。其他线程稍后会处理它。
                            break;
                        }
                    }

                }


            }

            unsafe void Refine(int workerIndex)
            {
                var threadPool = threadDispatcher.GetThreadMemoryPool(workerIndex);
                var subtreeCountEstimate = 1 << SpanHelper.GetContainingPowerOf2(MaximumSubtrees);
                var subtreeReferences = new QuickList<int>(subtreeCountEstimate, threadPool);
                var treeletInternalNodes = new QuickList<int>(subtreeCountEstimate, threadPool);

                CreateBinnedResources(threadPool, MaximumSubtrees, out var buffer, out var resources);

                int refineIndex;
                while ((refineIndex = Interlocked.Increment(ref RefineIndex)) < RefinementTargets.Count)
                {
                    Tree.BinnedRefine(RefinementTargets[refineIndex], ref subtreeReferences, MaximumSubtrees, ref treeletInternalNodes, ref resources, threadPool);
                    subtreeReferences.Count = 0;
                    treeletInternalNodes.Count = 0;
                }

                subtreeReferences.Dispose(threadPool);
                treeletInternalNodes.Dispose(threadPool);
                threadPool.Return(ref buffer);


            }

            void CacheOptimize(int workerIndex)
            {
                var startIndex = CacheOptimizeStarts[workerIndex];

                // 我们可以绕着走。但是我们也可以不这么做,因为这真的无关紧要！
                var end = Math.Min(Tree.nodeCount, startIndex + PerWorkerCacheOptimizeCount);
                for (int i = startIndex; i < end; ++i)
                {
                    Tree.IncrementalCacheOptimizeThreadSafe(i);
                }

            }
        }

        unsafe void CheckForRefinementOverlaps(int nodeIndex, ref QuickList<int> refinementTargets)
        {
            ref var node = ref Nodes[nodeIndex];
            ref var children = ref node.A;
            for (int childIndex = 0; childIndex < 2; ++childIndex)
            {
                ref var child = ref Unsafe.Add(ref children, childIndex);
                if (child.Index >= 0)
                {
                    for (int i = 0; i < refinementTargets.Count; ++i)
                    {
                        if (refinementTargets[i] == child.Index)
                            Console.WriteLine("Found a refinement target in the children of a refinement target.");
                    }

                    CheckForRefinementOverlaps(child.Index, ref refinementTargets);
                }

            }
        }

    }
}
